Pseudo random noise sequences (PN sequences) are used in many cryptographic and communications applications to provide randomly appearing symbols. Typically, cryptographic applications are methods to provide confidentiality of transmitted information through the use of stream ciphers. In communications systems, PN sequences may be used for example as spreading sequences in spread-spectrum communications systems where they determine the hop sequence and/or the direct spreading sequence.
In general a receiver of a spread-spectrum communications system will receive a digital signal/bit stream transmitted over a single carrier frequency which is combined from a digital signal/bit stream containing information such as a digitized voice and from a PN sequence used to code or encrypt the transmission. Typically, the length of the PN sequence stream is much larger than the length of the information stream thereby, complicating identification of ciphers containing the actual information.
In prior art, the PN sequences are sometimes derived by using a maximal length polynomial. Constructions, whether hardware or software implemented, which form PN sequences, in this manner are sometimes referred to as m-sequence generators. It is well known that the randomness properties of the sequences generated by the m-sequence generators are very limited as a result of a linear relationship between the symbols of the sequence. This enables prediction of the next symbol given sufficiently many but small number of previous symbols. This is not desirable in various applications, and hence there is a need for efficient techniques to enhance the unpredictability.
Clock control of the m-sequence generator is a well-known method that can be used to increase the unpredictability of m-sequence generators. The most frequent method of clock control is that of introducing two modes of operation in an m-sequence generator. In one mode the generator outputs the previously produced symbol, and in the other mode the generator outputs the next symbol from the m-sequence. The current mode can advantageously be determined by another PN sequence. Output bits generated by a clock controlled m-sequence generator form the PN sequences which are used, inter alia, to encrypt or spread an information signal.
The abovementioned method of clock control, also sometimes referred to as the stop-and-go method, is especially used in hardware applications where it is easy to implement this stop-and-go method. However, the randomness properties of the resulting sequence, although less predictable, are impaired by the fact that the output sequence contains repetitions of previous symbols. This may obviated by using a step-once or step-twice ((1,2)-step) scheme, i.e. a basic m-sequence generator generates the next symbol (mode 1) or the symbol after the next symbol (mode 2), instead of the stop-and-go scheme. When implementing such a clock controlled generator, the basic m-sequence generator is required to produce symbols at twice the rate of the rate needed for output symbols. Known solutions for this depend on the use of a higher internal clock rate for the basic m-sequence generator or on the use of a very complex hardware applications of clock controlled basic m-sequence generators.
EP 0905611 A2 discloses a pseudorandom number generating method and pseudorandom number generator where a selector selects a pseudorandom number Xj (a single bit) from either one of two function generator outputs on the basis of a previous pseudorandom number Xj−1. The two function generators generate data composed of a plurality of bits corresponding to state data held in a register. Another selector selects one of the data outputs of the function generators on the basis of the previous pseudorandom number Xj−1 and stores this in the register as state data.
The abovementioned pseudorandom generator in EP 0905611 A2 does not disclose a clock controlled multi-rate generator and is subject to the abovementioned deterioration of unpredictability, since a clock rate twice as high as the needed output rate is needed because only one symbol is output at a time.
U.S. Pat. No. 5,878,075 discloses a method of and an apparatus for generating a pseudorandom noise sequence (PN sequence), where a bit sequence of pseudorandom numbers is augmented by an extra bit in order to comply with the Interim Standard IS-95 for implementation of CDMA (Code Division Multiple Access), where a sequence of 215 bits is required.
Prior art methods and systems for generating PN sequences all require elaborate hardware and consequent expenditure of electrical power. There is therefore a need for a method and system for generating a PN sequence without the disadvantages of prior art.